package sort;

/**
 * 插入排序法 O(n^2)
 * 整个区间被分为
 *    1.有序区间
 *    2.无序区间
 * 每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入
 */
public class InsertionSort {
    // 5 1 3 4 2 9
    // 1 5 3 4 2 9
    // 1 3 5 4 2 9
    // 1 3 4 5 2 9
    // 1 2 3 4 5 9
    /** 直接插入排序 **/
    public static void insertionSort(int[] arr) {
        // i表示无序区间的起始位置
        for(int i = 1; i < arr.length; i++){
            //将无序区间的第一个元素插在有序区间的合适位置
//            for(int j = i; j > 0; j--){
//                if(arr[j] >= arr[j-1]){
//                    //当前的元素比前一个大，说明已经插到有序位置
//                    break;
//                }else{
//                    //插到前一个位置，再次循环比较
//                    swap(arr, j, j - 1);
//                }
//            }
            for(int j = i; j > 0 && arr[j] < arr[j-1]; j--){
                swap(arr, j, j - 1);
            }
        }
    }

    /** 折半插入排序 **/
    public static void insertionSortBS(int[] arr) {
        //i表示无序区间的起始位置
        for(int i = 1; i < arr.length; i++){
            //有序区间的左边界
            int left = 0;
            //有序区间的右边界
            int right = i;
            while(right > left){
                //有序区间的中间位置
                int mid = (left + right) / 2;
                if(arr[i] < arr[mid]){
                    //说明应该插入左半区间
                    right = mid;
                }else{
                    //说明应该插入左半区间
                    left = mid + 1;
                }
            }
            //此时left处就是应该插入的位置
            //则将[left,i-1]处的元素都向后移动一位
            int val = arr[i];
            for(int j = i; j > left; j--){
                arr[j] = arr[j-1];
            }
            arr[left] = val;
        }
    }

    //交换索引位置的元素值
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] + arr[j] - (arr[j] = arr[i]);
    }
}
